Route planning is an important problem for a number of applications including, but not limited to, autonomous robotics, navigation/guidance of air, naval, and ground vehicles, intelligent transportation systems, and space related applications (i.e., planetary rovers, etc.), as described, for example, in Y. Hwang et al., Gross Motion Planning-a survey, ACM Computing Surveys, 24(3): 219,291, September 1992; J. Latombe Robot Motion Planning, Kluwer, Boston, Mass. 1991; and R. Szczerba, New Cell Decomposition Techniques for Planning Optimal Paths, Doctoral Dissertation, University of Notre Dame, Notre Dame, Ind., 1996. Various applications require routes to have certain characteristics, parameters, and constraints depending on the application, or on the specific type of vehicle platform (aircraft, ship, tank, etc.).
When devising route planners, there are a number of desiderata which should be met to the extent possible, among which are real-time determination of relative costs for different types of vehicles in the presence of various types of environments. The result should be accurate, and should not rely on unrealistic approximations. The environment may be time-varying in nature, and may possibly even be represented by some sort of probability function (if exact locations are not known with a high degree of certainty). Furthermore, any such approach should be able to adapt, in real-time, to changing environmental conditions, given sufficient computing power.
Optimal solutions to the general case of route planning with the above-described constraints are considered to be NP-Complete in nature (corresponding to a particular class of problems in which no polynomial time solution is known to exist). Even if an optimal solution were to be found, which is believed to be unlikely, the convergence time and related memory requirements would likely be completely unrealistic for real-time applications using readily available processors. Thus, heuristic approaches have been used to generate efficient (based on computational and memory constraints) routes in real-time which are as good or better than a human could generate.
Most route planners for military operations are based on searching a digitized grid consisting of square cells of equal size. This technique is used because available terrain data generally comes from DTED (Digital Terrain Elevation Data) databases which are stored in grid-based formats. A route is then computed from a given "start" cell position to a "goal" cell position, with each cell representing a particular location in the environment. A cost estimation step is used to establish a "cost" value for a particular grid cell, corresponding to the cost incurred by an aircraft (or other vehicle) traveling through that particular region. This cost is used to represent any number of factors such as terrain features, threat exposure, weather conditions, cultural features, etc. The set of cost values for a particular environment is called its map cost (MC) array and is of size m.times.n , as described in C. Bodenhorn et al., Personalizing Onboard Route Re-Planning for Recon, Attack, and Special Operations Missions, 1997 American Helicopter Society Conference (Avionics and Crew Systems Technical Specialists Conference), September 1997; P. N. Stiles et al., Highly Parallelizable Route Planner based on Cellular Automata Algorithms, IBM Journal of Research and Development 38(2):167-181, March 1994; R. Szczerba et al., A Mission Adaptable Route Planner for Intelligent Guidance/Navigation Systems, 36th AIAA Conference (Aerospace Sciences Meeting and Exhibit), January 1998. A number of different route planning techniques use variations of such a cost array as input to compute the desired route. There are a very large number of different route planning techniques. A survey of various route planning algorithms, architectures, and techniques can be found in the Y. Hwang et al. and J. Latombe references.
Most route planners that use grid-based representations of the environment compare or correlate a proposed path segment in the form of a line overlayed on the square grid cell environment, to determine which grid cells the line intersects. A function is provided that adds up the relative cell costs (MC values) along cells lying on the particular segment of the route that is being considered in the route search process. The MC values of these cells are then added up and compared to the costs of other route segments being considered. FIG. 1 represents a portion of a simple grid-based map 10, showing the map cost for each cell or grid element. In FIG. 1, the cells are in a grid including five rows A, B, C, D, and E, and five columns 1, 2, 3, 4, and 5. All cells in row A have map values or costs of 34, and all cells in row B, except cell B5, have map costs of 34. Cell B5 has a map cost of 12. In row C, cells C1 and C2 each have a cost of 34, cell C3 has a cost of 88, C4 has cost 10, and C5 cost 23. In row D, the costs for columns 1, 2, 3, 4, and 5 are 34, 54, 33, 33, and 45, respectively. In row E, each cell has a map cost of 12. In FIG. 1, a line segment or path 12 represents a segment of a route. Line segment 12 intersects cells D1, D2, C2, C3, and C4. The cost of route segment 12 is determined by summing the map costs of cells D1, D2, C2, C3, and C4, which in the example is the sum of 34+54+34+88+10=220. In some cases, it may be desirable to average the cost per unit cell of the path traversed by the path segment, in order to more accurately assess the relative costs of equal-length path segments which happen to traverse different numbers of cells because of the differing directions of the path segments. A complete minimum-cost route is then generated by connecting various route segments which provide the least sum of map cost values.
The MC values of the grid cells of a grid map are usually computed off-line, taking into account data from a number of different sources. In determining the map cost, the cost of terrain features, threat exposure, cultural features (man-made features), etc. are all weighted and added together to generate the single cost value for each grid cell.